package com.LeeCode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 最小区间
 */

public class Code632 {
    public static void main(String[] args) {

    }

    public int[] smallestRange(List<List<Integer>> nums) {
        int total = 0;
        for (List<Integer> num : nums) {
            total += num.size();
        }
        int[][] pairs = new int[total][2];
        total = 0;
        for (int index = 0; index < nums.size(); index++) {
            for (int x : nums.get(index)) {
                pairs[total][0] = x;
                pairs[total][1] = index;
                total++;
            }
        }
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);

        int left = 0, count = 0, end = total - 1, start = 0;
        int[] cnt = new int[nums.size()];

        for (int right = 0; right < total; right++) {
            cnt[pairs[right][1]]++;
            if (cnt[pairs[right][1]] == 1) count++;

            while (count == nums.size()) {
                if (pairs[right][0] - pairs[left][0] < pairs[end][0] - pairs[start][0]) {
                    start = left;
                    end = right;
                }
                cnt[pairs[left][1]]--;
                if (cnt[pairs[left][1]] == 0) count--;
                left++;
            }
        }

        int[] ans = {pairs[start][0], pairs[end][0]};

        return ans;
    }
}
